#include <iostream>
using namespace std;
int n = 0;
struct lists {
	lists() {
        next = NULL;
	}

	lists(int x, int y) {
		coef = x;
		exp = y;
		next = NULL;
	}
	lists* add (lists *m, lists *m1){
		lists *res = m->next;
		lists *p = m->next;
		lists *q = m1->next;
		lists *pre = m;
		lists *tmp = NULL;
		while (p != NULL && q != NULL){
			if (p->exp < q->exp)
			{
			    pre = p;
				p = p->next;
			}
			else if (p->exp > q->exp)
			{
			    tmp = q->next;
				lists* q1 = new lists(q->coef, q->exp);
				pre->next = q1;
				q1->next = p;
				pre = q;
				q = tmp;
			}
			else
			{
				int x = p->coef + q->coef;
				if (x == 0)
				{
				    pre->next = p->next;
				    p = pre->next;
				}
				else
				{
				    p->coef = x;
				    pre = p;
					p = p->next;
				}
				tmp = q->next;
				q = tmp;
			}
		}
        if (q != NULL)
        {
            lists *res1 = res;
            for (int c = 0; c < n-1; c++)
            {
                res1 = res1->next;
            }
            res1->next = q;
        }
		return res;
	}
	lists* create() {
		lists* head = new lists();
		lists *p1 = head;
		cout << "请输入多项式项数" << endl;
		cin >> n;
		for (int i = 0; i < n; i++){
			int a = 0, b = 0;
			cout << "请输入系数和指数" << endl;
			cin >> a >> b;
			lists *p2 = new lists(a, b);
			p1->next = p2;
			p1 = p2;
		}
		cout << "多项式为：";
		lists *p3 = head->next;
		for (int j = 0; j < n; j++)
		{
			cout << p3->coef << "x^" << p3->exp << " ";
			if (j != n-1)
				cout << "+ ";
			p3 = p3->next;
		}
		cout << endl;
		return head;
	}
	int coef;
	int exp;
	lists *next;
};

int main(int argc, char** argv) {
	lists s;
	lists *p1 = s.create();
	lists *p2 = s.create();
	lists *p3 = s.add(p1, p2);
	lists *p = p3;
	int m = 0;
	while (p != NULL)
    {
        p = p->next;
        m++;
    }
	for (int j = 0; j < m; j++)
	{
		cout << p3->coef << "x^" << p3->exp << " ";
		if (j != m-1)
			cout << "+ ";
		p3 = p3->next;
	}
	cout << endl;
	return 0;
}

